#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

string s = "narek";

void solve()
{
    int n, m; cin >> n >> m;
    vector<int> dp(10, -100000000);
    dp[4] = 0;
    for (int i = 0; i < n; i++)
    {
        vector<int> ndp = dp;
        string temp; cin >> temp;
        for (int j = 0; j < 5; j++)
        {
            if (temp.find(s[j]) == s.npos) continue;
            int next = j;
            int num = 0;
            for (int k = 0; k < temp.size(); k++)
            {
                if (temp[k] == s[next])
                {
                    num += 1; next = (next + 1) % 5;
                }
                else if (temp[k] == 'n' || temp[k] == 'a' || temp[k] == 'r' || temp[k] == 'e' || temp[k] == 'k')
                {
                    num -= 1;
                }
            }
            ndp[(next + 4) % 5] = max(ndp[(next + 4) % 5], dp[(j + 4) % 5] + num);
        }
        dp = ndp;
    }
    int ans = 0;
    for (int i = 0; i < 5; i++) ans = max(ans, dp[i] - 2 * ((i + 1) % 5));
    cout << ans << endl;
}

int main()
{
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}